/*
 * @lc app=leetcode.cn id=51 lang=cpp
 *
 * [51] N 皇后
 */
#include <string>
#include <vector>
using std::string;
using std::vector;

// @lc code=start
class Solution
{
  private:
    void solveNQueens_helper(int n, int row, vector<std::string> &state, vector<bool> &cols, vector<bool> &diagonal1, vector<bool> &diagonal2, vector<vector<string>> &res)
    {
        /* 注意，row表示行数，从下标0开始，此处的返回条件表示row实际上已经超过了预定的n行，应该返回了 */
        if (row == n) {
            res.push_back(state);
            return;
        }

        for (int col = 0; col < n; ++col) {
            /* 计算主对角线，主对角线的值为（1-n,n-1)，所以+(n-1)，将其范围控制在(0,2*n-1)之间 */
            int main_diagonal = row - col + (n - 1);
            /* 计算次对角线 */
            int counter_diagonal = row + col;
            /* 当前列没有放置皇后，且主对角线上没有放置皇后，且次对角线上也没有放置皇后，则可以在当前列上放置皇后 */
            if (!cols[col] && !diagonal1[main_diagonal] && !diagonal2[counter_diagonal]) {
                /* 放置放皇后之后，当前列、主对角线和次对角线上应该标记为已经放置了皇后 */
                cols[col] = diagonal1[main_diagonal] = diagonal2[counter_diagonal] = true;
                state[row][col] = 'Q';
                solveNQueens_helper(n, row + 1, state, cols, diagonal1, diagonal2, res);
                /* 回溯，取消当前列、主对角线和次对角线上的标记 */
                cols[col] = diagonal1[main_diagonal] = diagonal2[counter_diagonal] = false;
                state[row][col] = '.';
            }
        }
    }

  public:
    vector<vector<string>> solveNQueens(int n)
    {
        vector<string> state(n, string(n, '.'));
        vector<vector<string>> res;
        vector<bool> cols(n, false);
        vector<bool> diagonal1(2 * n - 1, false);
        vector<bool> diagonal2(2 * n - 1, false);
        solveNQueens_helper(n, 0, state, cols, diagonal1, diagonal2, res);
        return res;
    }
};
// @lc code=end
